#include <iostream>
#include <vector>

using namespace std;
// 78.子集
// 给出一个集合，其中所有的元素各不相同。求出该集合的所有子集。(求含n个元素的集合的幂集。)

class Solution {
private:
    vector<vector<int>> res;
    // 记录回溯算法的递归路径
    vector<int> track;

    void backtrack(vector<int>& nums, int start) {
        // 前序位置，每个节点的值都是一个子集
        res.push_back(track);

        // 回溯算法的标准框架
        for(int i = start; i < nums.size(); i++) {
            // 做选择
            track.push_back(nums[i]);
            // 通过start参数控制树枝的遍历，避免产生重复的子集
            backtrack(nums, i+1);
            // 撤销选择
            track.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        res.clear();
        track.clear();

        backtrack(nums, 0);
        return res;
    }
};

void printMatrix(vector<vector<int>> arr) {
    for(int i = 0; i < arr.size(); i++) {
        cout<<"[";
        for (int j = 0; j < arr[i].size(); j++) {
            cout<<arr[i][j]<<",";
        }
        cout<<"],";
    }
    cout<<endl;
}
int main() {
    vector<int> nums1 = {1,2,3};
    vector<vector<int>> res1 = Solution().subsets(nums1);
    printMatrix(res1);

    vector<int> nums2 = {0};
    vector<vector<int>> res2 = Solution().subsets(nums2);
    printMatrix(res2);
    return 0;
}
